The present invention relates to a correlator and, more particularly, to a digital data correlator which detects the presence of a particular sequence of binary data bits in a serial binary data stream, is tolerant of data errors, and is adjustable to accept different numbers of data errors.
In the design of digital data communications equipment it is frequently necessary to detect the presence of a particular sequence of data bits in a received binary data stream. In particular, a sequence of data bits might be arranged as a code word, typically eight to thirty-two bits long, and be used as a marker in a serial data stream to delineate the start and end of data blocks or be inserted periodically in a data stream to mark the start of a frame of data. In order to process the data properly, it is generally necessary to detect the code word and adjust circuitry (e.g., digital counting circuits) to count in synchronism with the periodic code word. If the digital data stream is generated by distant communications equipment and is transmitted to the receiver without errors, the design of the logic circuitry needed to search the data for a perfect match to the transmitted code word is relatively straightforward and simple. However, practical data transmission systems always insert a small number of randomly distributed errors into the transmitted data stream.
If it is desired to detect a particular code word, given that some of the bits of the word are in error, the design problem becomes more difficult. For example, if the code word length is eight bits, and either one or two bit errors are to be allowed, there are thirty-six unique code patterns which are acceptable in addition to the perfect match. One possible solution to the above problem is to employ a comparison and error counting scheme implemented, by way of example, by a shift register having N stages or positions, where N represents the length of the code word desired to be detected in the incoming serial data stream. In this particular arrangement, the incoming serial data is shifted through the register and after each shift operation a series of counters and multiplexers are used to examine each of the N bit positions, one at a time, and count the number of bits in error. After all of the bit positions are tested, the error count is compared against a threshold count to determine whether the proper pattern is in the shift register. The above arrangement, while offering a workable solution, is expensive, requiring many counters and multiplexers, and is difficult to design due to the timing needed for controlling the logic. The greatest limitation, however, is speed. A clock of at least N times the input data rate is necessary to accomplish examination of the N bit positions before the next shift of data through the register. To emphasize this point, for a data rate of 512 kilobits/second and a data code word 18 bits long, the clock rate must be at least 9.216 MHz. Operations at these speeds require higher power logic than that needed to process data at 512 kilobits/second. Also, consideration must be given to the availability of such a high speed clock in any data receiving system.
Another solution to the above-described problem is to use outputs of a shift register as address lines to a memory (e.g., ROM, PROM, EPROM, etc.). In this arrangement, each combination of bits in the shift register selects a different location in the memory. The memory contains a logic "1" if the data pattern (address to memory) is acceptable or a logic "0" if the pattern is not acceptable. The above arrangement works well at high data rates, requiring no higher frequency clocks, but is expensive for moderate to large values of N (number of bits of the code word). By way of example, for N=18, a large and expensive memory of 262,144 (2.sup.N) locations is needed.